模拟赛题解/2025.9.29 模拟赛

T1-墙壁（wall）

题面

一个长为 $n$ 的排列 $a$，$i$ 被称为墙壁点，当且仅当满足 $1\leq i\leq n−2$ 且 $a_i,a_{i+1},a_{i+2}$ 可以作为一个非退化三角形的三边的长度。$T$ 组数据，每组数据给出 $n,m$，构造一个长为 $n$ 的排列，恰有 $m$ 个墙壁点。

$1\leq T\leq10^5,3\leq n,\sum n\leq3\times10^5,0\leq m\leq n-2$。

题解

首先构造无解当且仅当 $m=n-2$，尝试考虑 $m=0$ 的情况。

若要构造使每三个数都不满足条件，则可以尝试将每 $\frac n3$ 个数分开，然后三个分为一组。

则任意两数和一定可以构造为小于第三个数，考虑构造为对于每三个，大段和中段放最大的，小段放最小的，显然一定可行。

单次复杂度 $O(n)$，总复杂度 $O(\sum n)$。

T2-众数（wsx）

题面

给定一个整数 $n$，初始排列为 $a=[1,2,\cdots,n]$，即 $a[i]=i$（$1\leq i\leq n$）。 你需要处理 $q$ 个操作，操作有两种类型：

• $1$ $l$ $r$：查询区间 $[l,r]$ 上所有元素的和。
• $2$ $x$：将当前排列替换为它的下一个排列，重复 $x$ 次。例如，如果 $x=2$ 且当前 排列为 $[1,3,4,2]$，则执行如下变化链 $[1,3,4,2]\rightarrow [1,4,2,3]\rightarrow [1,4,3,2]$。

$2\leq n\leq2\times10^5,1\leq q\leq2\times10^5,1\leq x\leq10^5,\sum x\leq n!$。

题解

注意到实际上 $x$ 的改变范围使得只有最后 $14$ 位可能被改变。

直接暴力康托展开/逆康托展开，维护最后 $14$ 个元素即可。

复杂度 $O(q)$，常数较大，但是时间充裕。

T3-蹭网（network）

题面

在一条高速上有 $n$ 个城市。第 $i$ 个城市安装了一个功率为 $a_i$ 的天线，使其网络覆盖从 $L_i=\max(1,i−a_i)$ 到 $R_i=\min(n,i+a_i)$ 的所有城市。

一些大运会沿着这条路从城市 $s$ 移动到城市 $t$，其中 $s<t$。大运在经过的每个城市都会蹭覆盖该城市的某个网络。

因为更换蹭的网容易被网络管理发现，因此大运司机们切换网络的次数会尽可能少。用 $f(s,t)$ 表示从城市 $s$ 到城市 $t$ 的大运在途中蹭的网络改变次数（$s<t$）。初始在城市 $s$ 蹭的网不算作改变次数。

定义蹭网危险度 $F$ 为 $f(s,t)$ 的总和，即：

$$F=\sum^{n−1}_{s=1}\sum^n_{t=s+1}f(s,t)$$

现在大运司机们众筹了一个新天线，功率为 $x$。为了降低蹭网危险度，可以用新天线替换任意一个现有天线。你需要确定，如果最多替换一个天线为功率 $x$ 的新天线，危险度 $F$ 最小可能是多少。

$1\leq n\leq10^6,0\leq a_i,x\leq n$。

题解

首先考虑求出不更换天线时的 $F$。显然最优策略是在换网时选择覆盖当前点的天线中 $R_i$ 最大的蹭，并一直使用该网直至 $R_i+1$。发现该形式可以简单用 $\text{dp}$ 刻画。

记 $f_i$ 表示从城 $i$ 开始走到城 $[i,n]$ 的代价之和，$r_i$ 表示覆盖城 $i$ 的天线中最大的 $R$。则：$f_i=n-r_i+f_{r_i+1},F=\sum_{i=1}^nf_i$。记此时不带修改的 $F$ 为 $F_{st}$。

现在需要对于每个 $i$ 计算将 $a_i$ 替换成 $x$ 后的代价。注意到在仍保留天线 $a_i$ 的选择下，若 $x \leq a_i$ 则不会改变 $F$，否则与 $a_i$ 不存在的情况等价。因此可以不用去除 $a_i$ 的影响，直接考虑加入 $x$ 的影响。

（下记 $x$ 对应的 $L,R$ 为 $L_x, R_x$）

记 $l_i$ 表示覆盖城 $i$ 天线中最小的 $L_i$。则加入 $x$ 相当于使在区间 $[L_x, l_{R_x}-1]$ 中的 $j$ 的 $r_j$ 变成 $R_x$。

记经过上述区间的大运有 $c$ 辆，其原本贡献为 $S$，则新答案为：$F_{st} - S + c\,(n-R_x+f_{R_x+1})$。

从左往右处理 $i$，记 $g_i$ 表示从 $[1,i]$ 出发到 $i$ 的点数，转移为：$g_i = 1 + \sum_{r_j+1=i} g_j$。

则 $S$ 相当于区间内 $g_j f_{r_j+1}$ 的和，$c$ 相当于区间内 $g_j$ 的和。

从左到右扫描线，由于 $L_x, R_x$ 递增，边界只会改变 $O(N)$ 次，可以用 BIT 处理边界变化产生的贡献。

复杂度 $O(N \log N)$。

T4-冰霜行者（frost）

题面

大湖是一个完美的巨大的圆。圆上等距的分布着 $n$ 个港口，顺时针编号 $1$ 到 $n$，但是水里和外面的陆地有十分危险的存在，所以最开始港口间两两独立，互不可达。房主决定用冰霜行者在港口间直直地走出冰道。由于大湖真的很大，港口可以看作点，冰道可以看作线段。

依次发生 $m$ 个事件，每个事件形式如下：

• $1$ $u$ $v$ 表示房主在 $u,v$ 号港口间使用冰霜行者建造一条冰道；
• $2$ $u$ $v$ 表示询问 $u$ 号港口和 $v$ 号港口间是否可达。

单步可达的定义：连接了某个港口的冰道与该港口单步可达；任意位置相交的冰道间单步可达。单步可达关系是双向的。

可达的定义：可通过若干次单步可达走到。可以证明，可达关系是双向的，且有传递性。

$1\leq n\leq2\times10^5,1\leq m\leq3\times10^5$。

题解

注意到有效合并总共只有最多 $n-1$ 次，每次和之前所有边查一下哪些有交，再和端点合并。

首先断环成链，对于每个连通块只保留相邻链和最外层一条边。

根据题目性质，不同连通块间不可能有边相交，所以任意两个连通块要不然相离，要不然一个被夹在另一个的相邻两点间。

于是合并两个连通块只需要修改 $O(1)$ 条边。连通性仍然直接拿并查集维护。

现在的核心问题是怎么加新边：使用线段树维护每个点被边覆盖了几层，设其为 $h_i$。合并 $u < v$ 时如果穿过了某条边，那么一定穿过了 $u,v$ 间某个 $h_i < \max(u,v)$ 的点连出去的边。

找到 $u$ 右边第一个这样的 $i$，直接把它和 $u$ 各自所在连通块合并，然后重新试图合并新连通块最右端点和 $v$ 即可。

复杂度 $O(n\log n)$。